package mht.leetCode.primary.math;

import com.sun.tools.javac.util.StringUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Solution {

    /**
     * 【Fizz Buzz】
     *
     * 写一个程序，输出从 1 到 n 数字的字符串表示。
     *
     * 1. 如果 n 是3的倍数，输出“Fizz”；
     *
     * 2. 如果 n 是5的倍数，输出“Buzz”；
     *
     * 3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
     *
     * 示例：
     *
     * n = 15,
     *
     * 返回:
     * [
     *     "1",
     *     "2",
     *     "Fizz",
     *     "4",
     *     "Buzz",
     *     "Fizz",
     *     "7",
     *     "8",
     *     "Fizz",
     *     "Buzz",
     *     "11",
     *     "Fizz",
     *     "13",
     *     "14",
     *     "FizzBuzz"
     * ]
     */
    public List<String> fizzBuzz(int n) {

        if (n < 1) {
            return null;
        }

        List<String> list = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            String tmp;

            if (i % 3 == 0 && i % 5 == 0) {
                tmp = "FizzBuzz";
            } else if (i % 3 == 0) {
                tmp = "Fizz";
            } else if (i % 5 == 0) {
                tmp = "Buzz";
            } else {
                tmp = String.valueOf(i);
            }
            list.add(tmp);
        }

        return list;
    }

    /**
     * 【计数质数】
     *
     * 统计所有小于非负整数 n 的质数的数量。
     *
     * 示例:
     *
     * 输入: 10
     * 输出: 4
     * 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
     *
     */
    public int countPrimes(int n) {

        if (n <= 0) {
            return 0;
        }

        int count = 0;

        boolean[] flag = new boolean[n];//初始全都false

        for (int i = 2; i < n ; i++) {
            if (!flag[i]) {
                count ++;
                for (int j = 1; j * i < n ; j++)
                    flag[j * i] = true;
            }
        }
        return count;
    }

    /**
     * 【3的幂】
     *
     * 给定一个整数，写一个函数来判断它是否是 3 的幂次方。
     *
     * 示例 1:
     *
     * 输入: 27
     * 输出: true
     *
     * 示例 2:
     *
     * 输入: 0
     * 输出: false
     *
     * 示例 3:
     *
     * 输入: 9
     * 输出: true
     *
     * 示例 4:
     *
     * 输入: 45
     * 输出: false
     *
     * 进阶：
     * 你能不使用循环或者递归来完成本题吗？
     */
    public boolean isPowerOfThree(int n) {

        if (n < 0) {
            return false;
        }

        while (n % 3 == 0 && n / 3 != 0) {
            n = n / 3;
        }

        return n == 1;
    }

    /**
     * 【位1的个数】
     *
     * 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
     *
     * 示例 1：
     *
     * 输入：00000000000000000000000000001011
     * 输出：3
     * 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
     * 示例 2：
     *
     * 输入：00000000000000000000000010000000
     * 输出：1
     * 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
     * 示例 3：
     *
     * 输入：11111111111111111111111111111101
     * 输出：31
     * 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
     *
     */
    public int hammingWeight(int n) {

        // 思路：考察二进制操作
        int total = 0;
        for(int i = 0; i < 32; ++i) {
            total += (n & 1);
            n = n >> 1;
        }
        return total;

        // stream操作
//        return (int) Integer.toBinaryString(n).chars().filter(c -> '1' == c).count();
    }

    /**
     * 【颠倒二进制位】
     *
     * 颠倒给定的 32 位无符号整数的二进制位。
     *
     * 示例 1：
     *
     * 输入: 00000010100101000001111010011100
     * 输出: 00111001011110000010100101000000
     * 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     *       因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
     * 示例 2：
     *
     * 输入：11111111111111111111111111111101
     * 输出：10111111111111111111111111111111
     * 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     *       因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。
     *
     */
    public int reverseBits(int n) {

        int m=0;
        for(int i=0; i < 32; i++){
            m <<= 1;//m向左移1位；
            m = (n & 1);//m的末位设置为n的末位
            n >>= 1;//n向右移1位
        }
        return m;
    }

    /**
     * 【帕斯卡三角形】
     *
     * 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
     *
     * 在杨辉三角中，每个数是它左上方和右上方的数的和。
     *
     * 示例:
     *
     * 输入: 5
     * 输出:
     * [
     *      [1],
     *     [1,1],
     *    [1,2,1],
     *   [1,3,3,1],
     *  [1,4,6,4,1]
     * ]
     *
     */
    public List<List<Integer>> generate(int numRows) {

        List<Integer> tmp;
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; i++) {
            tmp = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    tmp.add(1);
                } else {
                    tmp.add(lists.get(i-1).get(j) + lists.get(i-1).get(j-1));
                }
            }
            lists.add(tmp);
        }
        return lists;
    }

    /**
     * 【有效的括号】
     *
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     *
     * 有效字符串需满足：
     *
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 注意空字符串可被认为是有效字符串。
     *
     * 示例 4:
     *
     * 输入: "([)]"
     * 输出: false
     * 示例 5:
     *
     * 输入: "{[]}"
     * 输出: true
     *
     */
    public boolean isValid(String s) {

        if (s.length() % 2 != 0 ) {
            return false;
        }

        Stack<Character> stack = new Stack<>();
        for (Character c : s.toCharArray()) {

            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.empty()) {
                    return false;
                }

                if (c == ')' && stack.pop() != '(')
                    return false;
                if (c == '}' && stack.pop() != '{')
                    return false;
                if (c == ']' && stack.pop() != '[')
                    return false;
            }
        }
        return stack.empty();
    }

    /**
     * 【缺失数字】
     *
     * 给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
     *
     * 示例 1:
     *
     * 输入: [3,0,1]
     * 输出: 2
     * 示例 2:
     *
     * 输入: [9,6,4,2,3,5,7,0,1]
     * 输出: 8
     * 说明:
     *
     * 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
     */
    public int missingNumber(int[] nums) {

        if (nums == null || nums.length < 1) {
            return 0;
        }

        Arrays.sort(nums);

        if (nums.length == 1 && nums[0] == 0) {
            return 1;
        }

        if (nums.length == 1 && nums[0] == 1) {
            return 0;
        }

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i-1] != 1) {
                return nums[i-1]+1;
            }
        }

        if (nums[0] != 0) {
            return 0;
        } else
            return nums[nums.length-1] + 1;
    }

    /**
     * 【汉明距离】
     *
     * 两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
     *
     * 给出两个整数 x 和 y，计算它们之间的汉明距离。
     *
     * 注意：
     * 0 ≤ x, y < 2^31.
     *
     * 示例:
     *
     * 输入: x = 1, y = 4
     *
     * 输出: 2
     *
     * 解释:
     * 1   (0 0 0 1)
     * 4   (0 1 0 0)
     *        ↑   ↑
     *
     * 上面的箭头指出了对应二进制位不同的位置。
     */
    public int hammingDistance(int x, int y) {
        int res = 0, exc = x ^ y;
        for (int i = 0; i < 32; ++i) {
            res += (exc >> i) & 1;
        }
        return res;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int res = solution.reverseBits(10000);
        System.out.println(res);
    }

}
